0786. 第 K 个最小的质数分数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 二分查找

1. 📝 题目描述

• leetcode

给你一个按递增顺序排序的数组 arr 和一个整数 k。数组 arr 由 1 和若干 质数 组成，且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.length 的 i 和 j，可以得到分数 arr[i] / arr[j]。

那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j]。

---

示例 1：

输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

示例 2：

输入：arr = [1,7], k = 1
输出：[1,7]

---

提示：

• 2 <= arr.length <= 1000
• 1 <= arr[i] <= 3 * 10^4
• arr[0] == 1
• arr[i] 是一个 质数，i > 0
• arr 中的所有数字 互不相同，且按 严格递增 排序
• 1 <= k <= arr.length * (arr.length - 1) / 2

进阶：你可以设计并实现时间复杂度小于 O(n^2) 的算法解决此问题吗？

2. 🎯 s.1 - 二分查找

c

int* kthSmallestPrimeFraction(int* arr, int arrSize, int k, int* returnSize) {
    double lo = 0, hi = 1;
    int* res = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;
    while (lo < hi) {
        double mid = (lo + hi) / 2;
        int cnt = 0, p = 0, q = 1, j = 1;
        for (int i = 0; i < arrSize; i++) {
            while (j < arrSize && arr[i] > mid * arr[j]) j++;
            cnt += arrSize - j;
            if (j < arrSize && (long long)p * arr[j] < (long long)q * arr[i]) { p = arr[i]; q = arr[j]; }
        }
        if (cnt == k) { res[0] = p; res[1] = q; return res; }
        if (cnt < k) lo = mid; else hi = mid;
    }
    return res;
}

js

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var kthSmallestPrimeFraction = function (arr, k) {
  const n = arr.length
  let lo = 0,
    hi = 1
  while (lo < hi) {
    const mid = (lo + hi) / 2
    let cnt = 0,
      p = 0,
      q = 1
    let j = 1
    for (let i = 0; i < n; i++) {
      while (j < n && arr[i] > mid * arr[j]) j++
      cnt += n - j
      if (j < n && p * arr[j] < q * arr[i]) {
        p = arr[i]
        q = arr[j]
      }
    }
    if (cnt === k) return [p, q]
    if (cnt < k) lo = mid
    else hi = mid
  }
  return []
}

py

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        lo, hi = 0.0, 1.0
        while lo < hi:
            mid = (lo + hi) / 2
            cnt = 0
            p, q = 0, 1
            j = 1
            for i in range(n):
                while j < n and arr[i] > mid * arr[j]:
                    j += 1
                cnt += n - j
                if j < n and p * arr[j] < q * arr[i]:
                    p, q = arr[i], arr[j]
            if cnt == k:
                return [p, q]
            if cnt < k:
                lo = mid
            else:
                hi = mid

• 时间复杂度：$O(n\log (1/ϵ))$，其中 n 是数组长度，$ϵ$ 是浮点精度
• 空间复杂度：$O(1)$

算法思路：

• 二分查找分数值 mid，统计小于等于 mid 的分数个数
• 利用数组有序性，用双指针高效统计，同时记录当前最大分数
• 当计数恍好等于 k 时，该最大分数即为答案